#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> pre;
    int n;
    int dfs(vector<int>& nums,int pos)
    {
        if(pre[pos]!=-1) return pre[pos];
        int ret=0;
        for(int i=pos+1;i<n;i++)
        {
            if(nums[i]>nums[pos])
            ret=max(ret,dfs(nums,i)+1);
        }
        pre[pos]=ret;
        return ret;
    }
    int lengthOfLIS(vector<int>& nums) {
        n=nums.size();
        pre=vector<int>(n,-1);
        int ret=0;
        for(int i=0;i<n;i++)
        {
            ret=max(dfs(nums,i)+1,ret);
        }
        return ret;
    }
};